Skip to content

Latest commit

 

History

History
91 lines (80 loc) · 3.2 KB

README.md

File metadata and controls

91 lines (80 loc) · 3.2 KB

1106. Parsing A Boolean Expression

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:

  • 't' that evaluates to true.
  • 'f' that evaluates to false.
  • '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr.
  • '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.
  • '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.

Given a string expression that represents a boolean expression, return the evaluation of that expression.

It is guaranteed that the given expression is valid and follows the given rules.

Example 1:

Input: expression = "&(|(f))" Output: false Explanation: First, evaluate |(f) --> f. The expression is now "&(f)". Then, evaluate &(f) --> f. The expression is now "f". Finally, return false.

Example 2:

Input: expression = "|(f,f,f,t)" Output: true Explanation: The evaluation of (false OR false OR false OR true) is true.

Example 3:

Input: expression = "!(&(f,t))" Output: true Explanation: First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)". Then, evaluate !(f) --> NOT false --> true. We return true.

Constraints:

  • 1 <= expression.length <= 2 * 104
  • expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

Solutions (Rust)

1. Solution

implSolution{pubfnparse_bool_expr(expression:String) -> bool{letmut ops = vec![];letmut bools = vec![];for ch in expression.chars(){match ch {'!' | '&' | '|' => ops.push(ch),'t' | 'f' => bools.push(Some(ch == 't')),')' => match ops.pop(){Some('!') => {let tmp = !bools.pop().unwrap().unwrap(); bools.pop(); bools.push(Some(tmp));}Some('&') => {letmut tmp = true;whileletSome(Some(b)) = bools.pop(){ tmp &= b;} bools.push(Some(tmp));}Some('|') => {letmut tmp = false;whileletSome(Some(b)) = bools.pop(){ tmp |= b;} bools.push(Some(tmp));} _ => {let tmp = bools.pop().unwrap(); bools.pop(); bools.push(tmp);}},'(' => bools.push(None), _ => (),}} bools[0].unwrap()}}
close